|
Project Euler (named after Leonhard Euler) is a website dedicated to a series of computational problems intended to be solved with computer programs. The project attracts adults and students interested in mathematics and computer programming. Since its creation in 2001 by Colin Hughes, Project Euler has gained notability and popularity worldwide.〔 〕 It includes over 500 problems,〔(【引用サイトリンク】title=Project Euler (list of problems) )〕 with a new one added every weekend (except during the summer). Problems are of varying difficulty but each is solvable in less than a minute using an efficient algorithm on a modestly powered computer. Problems can be sorted on difficulty. A forum specific to each question may be viewed after the user has correctly answered the given question.〔(【引用サイトリンク】title=Project Euler - About )〕 Project Euler has about 500,000 users from all over the world (who solved at least one problem).〔(【引用サイトリンク】title=Project Euler (Statistics) - not accessible for anonymous users )〕 Participants can track their progress through achievement levels based on the number of problems solved. A new level is reached for every 25 problems solved. Special awards exist for solving special combinations of problems, for instance there is an award for solving fifty prime numbered problems. A special Eulerians level exists to track achievement based on the fastest fifty solvers of recent problems so that newer members can compete without solving older problems.〔(【引用サイトリンク】title=Project Euler (News Archives) )〕 A subset of the Project Euler problems was used in an APL programming contest.〔(【引用サイトリンク】title=APL programming contest problem list )〕 There are 82 sequences〔(【引用サイトリンク】title=OEIS sequences referencing Project Euler problems )〕 in the On-Line Encyclopedia of Integer Sequences (OEIS) referencing Project Euler problems. == Example problem and solutions == The first Project Euler problem is If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Though this problem is much simpler than the typical problem, it serves to illustrate the potential difference that an efficient algorithm makes. The brute-force algorithm examines every natural number less than 1000 and keeps a running sum of those meeting the criteria. This method is simple to implement, as shown by the following pseudocode:
For harder problems, it becomes increasingly important to find an efficient algorithm. For this problem, we can reduce 1000 operations to a handful by using the inclusion–exclusion principle and a closed-form summation formula. : Here, denotes the sum of multiples of below . In big O notation, the brute-force algorithm is O(''n'') and the efficient algorithm is O(1) (assuming constant time arithmetic operations). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Project Euler」の詳細全文を読む スポンサード リンク
|